"Dependence analysis" is a term used in compiler technology to determine whether or not two array references in a loop of code may access the same memory location during execution. More formally, we say that a data dependence exists between two statements S.sub.1 and S.sub.2 if there is a path from S.sub.1 to S.sub.2 and both statements access the same location in memory.
Along with basic information on depdendence, most dependence analyzers also provide and indication of how many iterations of the loop can occur before the dependence occurs. This "distance vector" information is further explained later. As a simple example, consider: ##EQU1## In this case, regular alias analysis will not be able to determine whether A[i+3] and A [i+1] will certainly access the same memory location or not. It will only be able to tell that these two memory accesses may access the same location. However, dependence analysis technlology will precisely pinpoint the fact that the load will access the same location that was stored two iterations ago in the loop.
In the past decade, high performance computing has become increasingly important for may applications. Much progress has been made in developing large-scale parallel architectures composed of powerful commodity microprocessors. However, to effectively exploit parallelism and the memory hierarchy of these machines, compilers must be able to analyze data dependences precisely for array references in loop nests.
Calculating data dependence for arrays is complicated by the fact that two array references may not always access the same memory location. Dependence testing is the method used to determine whether dependences exist between two subscripted references to the same array in a loop nest. To illustrate, suppose that we wish to test whether or not there exists a dependence from statement S.sub.1 to S.sub.2 in the following model loop nest: ##EQU2##
Let .alpha. and .beta. be vectors of n integer indices within the ranges of the upper and lower bounds of the n loops in the example. There is a dependence from S1 to S2 if and only if there exists .alpha. and .beta. such that .alpha. is less than or equal to B and the following system of dependence equations is satisfied: EQU fi(.alpha.)=gi(.beta.) Vi, 1&lt;i&lt;m
Otherwise, the two references are independent. It is also known that dependences may be characterized by their access pattern between loop iterations using distance and direction vectors. Suppose that there exists a data dependence for .alpha.=(.alpha..sub.1, . . . , .alpha..sub.n) and .beta.=(.beta..sub.1, . . . , .beta..sub.n). Then the distance vector D=(D.sub.1, . . . , D.sub.n) is defined as .beta.-.alpha.. The direction vector d=(d.sub.1, . . . , d.sub.n) of the dependence is defined by the equation: d.sub.1 equals . . .
&lt;if .alpha..sub.1 &lt;.beta..sub.1 PA1 =if .alpha..sub.1 =.beta..sub.1 PA1 &gt;if .alpha..sub.1 &gt;.beta..sub.1
The elements are always displayed in order left to right, from the outermost to the innermost loop in the nest. For example, consider the following loop nest: ##EQU3##
The distance and direction vectors for the dependence between the definition and use of array A are (1, 0, -1) and (&lt;, =, &gt;), respectively. Since several different values of .alpha. and .beta. may satisfy the dependence equations, a set of distance and direction vectors may be needed to completely describe the dependence. Distance vectors specify the actual distance in loop iterations between two accesses to the same memory location. They may be used to guide optimizations to exploit parallelism or the memory hierarchy.
Dependence testing thus has two goals. First, it tries to disprove dependence between pairs of subscripted references to the same array variable. If dependences may exist, it tries to characterize them in some manner, usually as a minimal complete set of distance and direction vectors. Dependence testing must also be conservative and assume the existence of any dependence it cannot disprove. Otherwise the validity of any optimizations based on dependence information is not guaranteed. Various techniques are known in the prior art for making dependence determinations, but they are computationally very expensive.
"Memoization" is not a misspelling--it is known in computer science as a technique for recording and remembering the results of previous computations, so that repeating the same computations can be avoided. A memorization technique has been suggested to save the results of data dependence tests in order to avoid calling the data dependence routines multiple times on the same input. See, Dror Maydan, et al., "Efficient and Exact Data Dependence Analysis" (Computer Systems Labs, Stanford University, published in the Proceedings of the ACMSIGPLAN 1991). However, known memoization is limited to a single compilation of a single file, and therefore has limited utility. The need remains to provide more efficient ways for compilers to handle dependence issues.